package org.dormi.learn.definition;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.*;

/**
 * @author : dormi330
 * @since : 2021/1/27/0027
 * 图的定义
 */
public class Graph {
    private static final Logger log = LoggerFactory.getLogger(Graph.class);

    /** 所有顶点 */
    private final Set<Vertex> vertices = new HashSet<>();

    /** 邻接表的map key=顶点 */
    private final Map<Vertex, Adjacence> adjMap = new HashMap<>();

    private Vertex entry;

    public Graph() {
    }

    public Vertex addVertex(Vertex v) {
        Vertex origin = null;
        for (Vertex aVertex : vertices) {
            if (aVertex.equals(v)) {
                origin = aVertex;
                break;
            }
        }

        if (origin == null) {
            log.info("addVertex, [{}]", v);
            origin = v;
            vertices.add(origin);
            Adjacence adj = new Adjacence(origin);
            adjMap.put(origin, adj);
        } else {
            log.debug("addVertex, 顶点[{}]已存在", origin);
        }

        return origin;
    }

    /** 统计图中每个vertex的出入度 */
    public void countDegree() {
        /* 节点的出度 = 邻接表的大小 */
        for (Adjacence adj : adjMap.values()) {
            adj.src.setOutDegree(adj.size());
        }

        /* 统计入度: 对每条边, 边 dst节点的入度+1 */
        for (Adjacence adj : adjMap.values()) {
            for (Edge e : adj) {
                e.dst.incInDegree();
            }
        }
    }

    /** 添加一条边 */
    public void addEdge(Vertex v1, Vertex v2, int weight) {
        Vertex v1Real = addVertex(v1);
        Vertex v2Real = addVertex(v2);

        // 这样=, 不是equals
        if (v1Real == v2Real) {
            log.warn("节点[{}]指向自身, 跳过", v1Real.id);
            return;
        }
        adjMap.get(v1Real).addEdge(v2Real, weight);
    }

    public void addEdge(List<Edge> edges) {
        for (Edge e : edges) {
            addEdge(e.src, e.dst, e.weight);
        }
    }

    /** dfs后, 移除 back edge */
    public void removeBackEdgeAfterDFS() {
        for (Adjacence adj : adjMap.values()) {
            if (adj.size() == 0) {
                continue;
            }

            /* 在edge u -> v中, 如果
             * arrive[u]    > arrival[v]
             * departure[u] < departure[v]
             * 则是 back edge
             */
            Set<Edge> toRemove = new HashSet<>(adj.size());
            int arrivalU = adj.src.getArrival();
            int departureU = adj.src.getDeparture();

            for (Edge edge : adj) {
                Vertex v = edge.dst;
                int arrivalV = v.getArrival();
                int departureV = v.getDeparture();
                if (arrivalU > arrivalV && departureU < departureV) {
                    toRemove.add(edge);
                    log.info("remove edge[{} ->{}]", adj.src.id, v.id);
                }
            }

            if (!toRemove.isEmpty()) {
                adj.removeAll(toRemove);
            }
        }
    }

    @Override
    public String toString() {
        return "Graph{" +
                "vertices=" + vertices +
                ", adjMap=" + adjMap +
                ", entry=" + entry +
                '}';
    }

    public void setEntry(Vertex v) {
        Vertex real = addVertex(v);
        this.entry = real;
    }

    public Set<Vertex> getVertices() {
        return vertices;
    }

    public Vertex getEntry() {
        return entry;
    }

    public Map<Vertex, Adjacence> getAdjMap() {
        return adjMap;
    }

}
